package com.mgq.algorithm.array;

/**
 * @author MaGuangQi
 * @description https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 * 第24题
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * <p>
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * 示例:
 * <p>
 * 给定 1->2->3->4, 你应该返回 2->1->4->3.
 * @date 2020-06-13 20:38
 **/
public class SwapPairs {

    /**
    *解法一: 使用递归
     * 使用递归来解决问题,主要是递归的三部曲
     * 一:找到终止条件, 本题的终止条件是节点为空,或者节点的下个节点为空
     * 二:找返回值, 返回给上一次的递归的应该是一个交换后的子链表
     * 三:单次的过程: 每次递归的单次过程应该是 前节点   当前节点  和已经完成交换后的子链表,那么要完成交换,只需要交换
     * 前节点和当前节点.并将前节点指向 交换后的子链表
    */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //注意步进是2, 因为每次交换2个
        //tmp应该是返回的已经交换后的子链表
        ListNode next = head.next;
        ListNode tmp = swapPairs(next.next);
        //单次过程
        //head是前一个节点
        //head.next是当前节点
        //tmp是返回的已经交换后的子链表

        //2 ->3 -> 交换后
        //变成 3->2 ->交换后

        //开始交换
        next.next=head;
        head.next=tmp;
        //返回已经交换完后的子链表.不是tmp,相当于每次返回都是新的. tmp是上一次返回的子链表
        return head.next;

    }
    /**
    *解法二: 使用指针
     * 这种解法就是返回值比较难处理, 我们可以使用一个临时节点,这个临时节点一开始指向头节点
     * 我们需要在循环中把真正的头节点给这个临时节点的next. 其他就是每次把相邻的链表交换了就行
     * 返回临时节点的next不就是新的链吗?
    */
    public ListNode swapPairs2(ListNode head) {
        //初始化一个prevNode节点,代表前节点
        ListNode prevNode = new ListNode(-1);
        prevNode.next=head;
        ListNode finish=prevNode;
        while (head != null && head.next != null) {
            ListNode firstNode=head;
            ListNode secondNode = head.next;
            //开始交换
            //把secondNode的下个节点赋值给firstNode的next,相当于交换
            firstNode.next=secondNode.next;
            secondNode.next=firstNode;
            prevNode.next=secondNode;
            //交换完成
            prevNode=firstNode;
            head= prevNode.next;
        }
        //finish.next是一个新链
        return finish.next;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
}
